1. Field of the Invention
In general, the invention relates to database management. More particularly, the invention relates to methods, systems and program product for redundant, multi-dimensional data partitioning.
2. Background Discussion
The need for reliable and efficient storage of large amounts of complex data continues to increase dramatically. Indeed, while there have been great advances in storage technology, for example, the increasing capacity and decreasing cost of hard disks, the need for extensive storage seems to have outpaced these advances. As a result, storage of truly large amounts of data on a single server is in many cases impractical and a distributed approach is desirable. Moreover, even in those cases where storage can be handled by a single machine, a distributed database may offer superior reliability and more efficient load handling.
Typically, implementing a database in a distributed manner involves partitioning. Partition of a database may be defined as “a division of a logical database or its constituting elements into distinct independent parts.” In many distributed databases, each partition is stored at one node within the distributed database. While the physical architecture of a database need not have a one-to-one correspondence with the logical structure of the database, it is often the case that each node is stored on a separate server. In such cases, partitioning distributes the storage requirements across multiple machines, thus increasing the total storage capability of the database. Moreover, if a transaction, such as an ‘INSERT’ or ‘SELECT’, only requires access to data stored within one partition, the transaction may be executed by accessing only a single node. Other nodes remain free to handle other transactions concurrently, increasing the load handling capabilities of the database as a whole.
The technique of routing queries to the appropriate nodes based on a partitioning strategy is commonly known as partition pruning. There are reports that partition pruning can often improve query performance by several orders of magnitude. For example, in the case of a database that contains a record of orders, partitioned by week, a query requesting orders for a single week need only access a single partition. If the table had 2 years of historical data, this query could access only a single partition to satisfy the query, instead of all 104 partitions. This query could potentially execute 100 times faster, simply because of the partition pruning. Oracle Corporation, Partitioning in Oracle Database 11g, white paper (2007). Much of the skill in devising an effective partitioning strategy thus involves anticipating common transactions and partitioning such that the common transactions can be handled by a single node.
For purposes of further illustration, consider a database storing data items in the form of tuples of length N, expressed as:I=(k1,k2, . . . ,kj, . . . ,kN).  (1)where kj are values, selected from the jth key within a list of N keys.
Each key within the key list is defined by an ordered list of values vi. A key may thus be expressed as:Kj={v1,v2, . . . ,vi, . . . ,vMj}.  (2)
In many instances, the ordered list of values is simply a range of integers. For example, a key may be defined as the integers between 1 and 10, inclusive. That is:Kx=[1,10].  (3)Thus, for a key list S of N=2 keys defined as:S={K1,K2}={[2, 7], [4, 13]},  (4)one possible tuple is:I=(3,8).  (5)
Accordingly, the set of all possible tuples can be considered as an N-dimensional tuple space, with each dimension corresponding to the range of possible values for a particular key within the key list.
In one commonly used partitioning method, termed horizontal partitioning, partitions are created by segmenting a tuple space along a single dimension. The term “horizontal” derives from an alternative paradigm of viewing data within the database as rows within tables. In horizontal partitioning, the partitions are divided by lines parallel to the table rows, which are horizontal. A graphical representation of horizontal partitioning is shown in FIG. 1, in which a 2-dimensional tuple space is partitioned along the x-dimension into three partitions N1, N2, and N3 102-106. As shown in FIG. 1, the partition boundaries need not correspond to “horizontal” lines in the tuple space.
The boundaries of the partitions are defined by key ranges within the key corresponding to the dimension along which partitioning occurs; for example, the x-dimension in FIG. 1. Here, a key range is a contiguous subset of the indices into the ordered list of values that define a key. A key range on a key Kj is expressed by a pair of values representing the ends of the range, inclusively; that is:ri=[vmin,vmax].  (6)
Partitioning can be thus understood as assigning a storage location—in other words, a node on which storage will occur—based on the location of the stored tuple within the tuple space. As a more specific example, suppose the dimensions x and y correspond to a key list:S={K1,K2}={[0,99999],[‘ - - - ’,‘ZZZZZZ’]},  (7)with K1 (and the x-dimension) representing 5-digit zip codes and K2 (and the y-dimension) representing six-letter first names of customers. One possible horizontal partitioning strategy consistent with FIG. 1 is defined by the key ranges:r11=[0,33332],  (8)r21=[33333,66665], and   (9)r31=[66666,99999];  (10)where tuples having k1 in r11 are stored by node N1, tuples having k1 in r21 are stored by node N2, and tuples having k1 in r31 are stored by node N3. This partitioning strategy is well-suited to handling transactions that access tuples within a range restricted along the x-dimension. For example, the select statement:
SELECT  K1FROM  SWHERE  K1 = 90210can be handled by node N3 alone. Similarly, a partitioning strategy defined by the key ranges:r12=[‘ - - - ’,‘Davis-’]  (11)r22=[‘Davisa,‘Smith-’]  (12)r32=[‘Smitha’,‘ZZZZZZ’]  (13)is well-suited to handling transactions that access tuples within a range restricted along the y-dimension. However, the first strategy provides no benefit in handling transactions that access tuples within a range restricted along the y-dimension, and the second strategy provides no improvement in handling transactions that access tuples within a range restricted along the x-dimension. Thus, horizontal partitioning provides no increase in access efficiency in handling transactions restricted along a dimension other than the single partitioned dimension.
Another commonly used partitioning method, termed composite partitioning, allows the tuple space to be partitioned along more than one dimension. As described in the 2007 Oracle White Paper, “the table is partitioned by data distribution method one and then each partition is further subdivided into sub-partitions using a second data distribution method. All sub-partitions for a given partition together represent a logical subset of the data.” This method is illustrated in FIG. 2. Here, the tuple space is first partitioned along the x-dimension using a set of key ranges {r11, r21, r31}, yielding partitions 202-206 of the form shown in FIG. 1. Then, the tuple space is sub-partitioned 208-212 along the y-dimension using a set of key ranges {r12, r22, r32} shown in FIG. 2. The tuples stored at node N1 in FIG. 1 are thus allocated across nodes N1,1, N1,2, and N1,3.
Composite partitioning is well-suited to handling transactions that access tuples within a range restricted along both the initially and sub-partitioned dimensions. For example, if the tuple space of Equation 7 is partitioned using the key ranges of Equations 8-10 and then along the key ranges of Equations 11-13, the query statement:
SELECT  K1, K2FROM  SWHERE  K1 = 90210 and K2 = ‘Morris’can be handled by node N3,2 alone. Composite partitioning, however, provides lesser benefits when handling transactions that access tuples within a range restricted along a single dimension. In the above example, a statement of the form:
SELECT  K1, K2FROM  SWHERE  K1 = 90210must be handled by accessing nodes N31, N3,2, and N3,3. Similarly, the statement:
SELECT  K1, K2FROM  SWHERE  K2 = ‘Morris’must be handled by accessing nodes N1,2, N2,2, and N3,2. Thus, in spite of the fact that the database has been partitioned into 9 nodes, handling such transactions requires access to 3 nodes. While this 3:1 increase in access efficiency matches that provided by the partitioning strategy of FIG. 1, it is less than the 9:1 optimal efficiency suggested by the existence of 9 nodes.
Generalizing, let SN be an N-dimensional tuple space, partitioned along each of M dimensions constituting SM, where SM⊂SN. For a transaction with R restrictions along the R dimensions constituting SR, the number of nodes that must be accessed to handle the transaction is:
                                          A            ⁡                          (                              S                R                            )                                =                                                    ∏                                  i                  ∈                                      S                    M                                                              ⁢                                                          ⁢                              p                i                                                                    ∏                                  j                  ∈                                      S                                          R                      ′                                                                                  ⁢                                                          ⁢                              p                j                                                    ,                            (        14        )            where SR′=SR∩SM and pk denotes the number of partitions along the kth dimension in SM. Considering the ratio of the total number of nodes to the number of nodes that must be accessed provides a measure of the increase in efficiency made possible by the partitioning strategy, namely:
                    E        =                                                            ∏                                  i                  ∈                                      S                    M                                                              ⁢                                                          ⁢                              p                i                                                    A              ⁡                              (                                  S                  R                                )                                              =                                    ∏                              j                ∈                                  S                                      R                    ′                                                                        ⁢                                                  ⁢                                          p                j                            .                                                          (        15        )            
Therefore, to the extent that the restrictions on a transaction do not restrict along all of the partition dimensions—to the extent that SR≠SM—the increase in access efficiency provided by composite partitioning strategies does not match the maximum increase in efficiency suggested by the number of partitions.
The foregoing analysis of access efficiency is somewhat simplified because it assumes that the restrictions are narrow enough to require access to tuples within only one of the ranges specified along each restricted dimension. Although not all transactions are so restricted, it is nevertheless a useful analysis for indicating the typical increase in access efficiency offered by a particular partitioning strategy.